package com.berchen.数据结构.二叉树.二叉排序树;

import lombok.Data;

/**
 * 二叉排序树（BST）
 * 添加节点思路：小于当前节点的放左边，大于当前节点的放右边
 * 删除节点思路：
 *  找到要删除的节点targetNode
 *  找到要删除的节点的父节点 parent
 *  如果删除的节点是叶子节点  直接删除即可。
 *  如果删除的是一个子树的节点
 *  targetNode是父节点的左子节点
 *      子树是targetNode的左：parent.left=targetNode.left
 *      子树是targetNode的右：parent.left=targetNode.right
 *  targetNode是父节点的右子节点
 *      子树是targetNode的左：parent.right=targetNode.left
 *      子树是targetNode的右：parent.right=targetNode.right
 *
 *  如果删除的是两个子树的节点：
 *      找到targetNode的左子树的最大节点 或者找到targetNode的右子树的最小节点
 *      然后用上一步找到的节点替换要删除的节点即可
 *
 */
@Data
public class BinarySortTree {
    private BinarySortNode root;

    /**
     * 删除节点
     * @param value
     */
    public void delNode(int value){
        if(root==null){
            return;
        }
        BinarySortNode targetNode=getDelNode(value);
        if(targetNode==null){
            return;
        }
        if(root.left==null&&root.right==null){
            root=null;
            return;
        }
        BinarySortNode delParent = getDelParent(value);
        if(targetNode.left==null&&targetNode.right==null){
            // 删除叶子节点
            if(delParent.left!=null&&delParent.left.value==value){
                delParent.left=null;
            }
            if(delParent.right!=null&&delParent.right.value==value){
                delParent.right=null;
            }
        }else if(targetNode.left!=null&&targetNode.right!=null){
            // 删除两个子节点的树
            if(delParent!=null) {
                BinarySortNode minNode = getMinNode(targetNode, false);
                minNode.left = targetNode.left;
                minNode.right = targetNode.right;
                if (delParent.left != null && delParent.left.value == value) {
                    delParent.left = minNode;
                }
                if (delParent.right != null && delParent.right.value == value) {
                    delParent.right = minNode;
                }
            }else {// 父节点为null
                BinarySortNode minNode = getMinNode(targetNode, false);
                minNode.left = targetNode.left;
                minNode.right = targetNode.right;
                root=minNode;
            }
        }
        else{
            // 删除一个节点的树
            if(delParent!=null) {
                if (delParent.left != null && delParent.left.value == value) {
                    if (targetNode.left != null) {
                        delParent.left = targetNode.left;
                    } else {
                        delParent.left = targetNode.right;
                    }
                } else if (delParent.right != null && delParent.right.value == value) {
                    if (targetNode.left != null) {
                        delParent.right = targetNode.left;
                    } else {
                        delParent.right = targetNode.right;
                    }
                }
            }else {// 父节点为null

                if(targetNode.left!=null&&targetNode.left.value==value){
                    root=targetNode.left;
                }
                if(targetNode.right!=null&&targetNode.right.value==value){
                    root=targetNode.right;
                }
            }
        }
    }

    /**
     * 找到node为根节点的树的左子树的最大值 还是找到node为根节点的树的右子树的最小值 并且同时删除该节点
     * @param node
     * @param flag  true  左子树的最大值   false 右子树的最小值
     * @return
     */
    public BinarySortNode getMinNode(BinarySortNode node,boolean flag){

        if(node==null){
            return null;
        }
        BinarySortNode temp=node;
        if(flag){
            if(temp.left!=null) {
                temp=temp.left;
                while (temp.right!= null){
                    temp= temp.right;
                }
                delNode(temp.value);
                return temp;
            }
        }
        else {
            if(temp.right!=null){
                temp=temp.right;
                while (temp.left!=null){
                    temp=temp.left;
                }
                delNode(temp.value);
                return temp;
            }
        }
        return null;
    }

    /**
     * 获取要删除节点的父节点
     * @param value
     * @return
     */
    public BinarySortNode getDelParent(int value){
        if(root==null||root.value==value){
            return null;
        }
        return getDelParent(root,value);
    }
    private BinarySortNode getDelParent(BinarySortNode node,int value){
        if(node==null){
            return null;
        }
        if((node.left!=null&&node.left.value==value)||(node.right!=null&&node.right.value==value)){
            return node;
        }
        BinarySortNode temp=null;
        if(node.left!=null){
            temp= getDelParent(node.left,value);
        }
        if(temp==null&&node.right!=null){
            temp=getDelParent(node.right,value);
        }
        return temp;
    }

    /**
     * 获取要删除的节点
     * @param value
     * @return
     */
    public BinarySortNode getDelNode(int value){

        return getDelNode(root,value);
    }
    private BinarySortNode getDelNode(BinarySortNode node,int value){
        if(node==null){
            return null;
        }
        if(node.value==value){
            return node;
        }
        BinarySortNode temp=null;
        if(node.left!=null){
            temp= getDelNode(node.left,value);
        }
        if(temp==null&&node.right!=null){
            temp=getDelNode(node.right,value);
        }
        return temp;
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (root == null) {
            System.out.println("二叉排序树为null");
        } else {
            infixOrder(root);
        }
    }

    public void infixOrder(BinarySortNode node) {

        if (node.left != null) {
            infixOrder(node.left);
        }
        System.out.println(node);
        if (node.right != null) {
            infixOrder(node.right);
        }
    }

    /**
     * 往二叉排序树中添加元素
     *
     * @param node
     */
    public void add(BinarySortNode node) {

        if(root==null){
            root=node;
        }else {
            BinarySortNode temp = root;
            while (true) {
                if (temp == null) {
                    temp = node;
                } else {
                    // 放右边
                    if (temp.value <= node.value) {
                        if (temp.right == null) {
                            temp.right = node;
                            break;
                        } else {
                            temp = temp.right;
                        }
                    } else {
                        // 放左边
                        if (temp.left == null) {
                            temp.left = node;
                            break;
                        } else {
                            temp = temp.left;
                        }
                    }
                }
            }
        }
    }
}
